import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        for(int i=0;i<n;i++){
            long a=scanner.nextLong();
            long b=scanner.nextLong();
            System.out.println(add(a,b));
        }
        scanner.close();
    }
    public static long add(long a,long b){
        long sum=0;
        while(a!=0&&b!=0){
            if(a>b){
                a=a-b;
            }else{
                b=b-a;
            }
            sum++;
        }
        return sum;
    }
}